#include "../comm.h"

class Solution {
public:
    // 核心：动态的找到数组中比一个数大的个数
    // 如何使用树状数组维护
    // 每次插入的时间复杂度是O(log(n)), 每次查询时间复杂度是log(n)

    inline int lowbit(int x) { return x & -x; }

    // 从树状数组中查询小于等于当前数的个数
    int query(int x, vector<int>& tree)
    {
        int id = index[x];
        int ans = 0;
        for (int i = id; i; i -= lowbit(i))
            ans += tree[i];
        return ans;
    }

    // 将当前数加入树状数组中
    void add(int x, vector<int>& tree, vector<int>& ans)
    {
        ans.push_back(x);
        int id = index[x];
        for (int i = id; i < tree.size(); i += lowbit(i))
            tree[i]++;
    }
    unordered_map<int, int> index;
    vector<int> resultArray(vector<int>& nums) {
        index.clear();
        // 由于数据量比较多，需要进行离散化
        vector<int> sortNum = nums;
        sort(sortNum.begin(), sortNum.end());
        for (int i = 0; i < sortNum.size(); ++i)
            index[sortNum[i]] = i + 1;
        vector<int> tree1(nums.size() + 1);
        vector<int> tree2(nums.size() + 1);
        vector<int> ans1, ans2;
        add(nums[0], tree1, ans1), add(nums[1], tree2, ans2);
        for (int i = 2; i < nums.size(); ++i)
        {
            int e = nums[i];
            int tree1_n = ans1.size(), tree2_n = ans2.size();
            int num1 = tree1_n - query(e, tree1);
            int num2 = tree2_n - query(e, tree2);
            // cout << e << ' ' << num1 << ' ' << num2 << endl;
            if (num1 > num2) add(e, tree1, ans1);
            else if (num1 < num2) add(e, tree2, ans2);
            else
            {
                if (tree1_n <= tree2_n) add(e, tree1, ans1);
                else add(e, tree2, ans2);
            }
        }
        for (auto e : ans2)
            ans1.push_back(e);
        return ans1;
    }
};